1. Technical Field
The invention relates to computers. More particularly, the invention relates to compiler technology that provides improved memory layout of automatic variables declared in a user program, commonly referred to as storage allocation.
2. Description of the Prior Art
Prior solutions to variable storage allocation by compilers allocated variables in memory in the order that they appear in a source program. This approach has the benefit of allowing for easily determined address ordering of variables. There are several patents that describe improvements to standard storage allocation techniques.
The following patents discuss storage allocation techniques that operate on dynamic information, i.e. during run-time:
S. Wei, Self-Tuning Virtual Storage Management For Dedicated Real-Time Computer System, U.S. Pat. No. 5,367,637 (Nov. 22, 1994) discloses a self-tuning method for the management of virtual storage in a dedicated real-time computer system that interposes a layer between the application and the real-time computer system to form a two-layer structure to meet an application's request for virtual storage, i.e. a buffer request. The method adds the slower allocation of the real-time system (layer two) to guarantee the creation of all other buffers during one real-time period. The self-tuning layer (layer one) is checked first to satisfy a buffer request, while the untuned second layer is entered to create a buffer when the first layer fails. Entrances to the second layer are used to monitoring mechanism from which a new pre-allocation definition, based on system usage history, is derived to tune the first layer at the next initialization time.
K. Karrick, Dynamic Allocation In A Logic Analyzer, U.S. Pat. No. 5,347,540 (Sep. 13, 1994) discloses a dynamic memory allocation scheme that conserves memory resources while providing interaction between concurrent synchronous and asynchronous acquisition of data for logic analysis.
W. Ashcraft, G. Woodside III, G. Currington. K. Robb, Method of Virtual memory Storage Allocation With Dynamic Adjustment, U.S. Pat. No. 5,247,60 (Sep. 21, 1993) discloses a method for dynamically managing the storage of information in a mass memory of a data processor, where the mass memory includes a plurality of volumes of write-once media such as optical discs. The volumes are grouped into volume sets which each contain at least one file set. The size of the file sets and volume sets is dynamically increased as needed during file storage.
The following patent discusses storage allocation techniques that operate in a garbage collection environment, i.e. a space optimization technique in which superfluous data are eliminated. Because such approaches are inherently dynamic, they do not address the static compilation of an application:
J. Gurd, K. Kawakami, Storage Allocation and Garbage Collection Using Liberate Space Tokens, U.S. Pat. No. 5,025,367 (Jun. 18, 1991) discloses a parallel storage allocation method in which each space in a memory section that is available for use is associated with a respective allocator. The method stores an identifier for the respective allocator. Data identifying allocators not in use are stored, and a list is maintained of allocators associated with spaces which are available for use. Each time a memory space is no longer in use a check is made to determine the allocator identifier of any already free space which can be combined with the memory space that is no longer in use. A liberate space token is generated that includes a first identifier that corresponds to an allocator which is not in use and a second identifier that correspond to any already free space to be combined.
The following patents discuss storage allocation techniques that operate on secondary storage:
H. Pennings, H. Wijgen, Method of Changing Data on Disc, U.S. Pat. No. 5,113,509 (May 12, 1992) discloses an input/output test and set operation for testing and changing data in an access status record on a direct access storage device in one atomic input/output operation.
R. Clifton, R. Phares, Method and Apparatus for Assigning Data Sets to Virtual Volumes in a Mass Store, U.S. Pat. No. 4,310,883 (Jan. 12, 1982) discloses a mass storage system having a multiplicity of storage volume containing addressable data in which the assignment of newly received data sets to the best storage volume is accomplished by determining the best match of the data set to the available volume.
See, also the following documents:
Research Disclosure No. RD 274,059 (Derwent WPI Acc. No. 87-077601/11), dated Feb. 10, 1987, "Dynamic Reorganization of Disc Storage Allocation Using Controller to Periodically Move Data Most Frequently Accessed to Portion of Disc With Shortest Access Time," discloses a device controller is programmed to periodically examine dynamic usage information to determine if a logical cylinder has become more active. If the cylinder become more active, then its informational contents are copied to a preferred area on a storage disk that is for high activity.
Oldehoeft, R. R., Allan, S. J., Adaptive exact-fit storage management, Communications of the ACM, vol. 21, no. 5 discusses storage allocation techniques that operate on dynamic information (during run-time).
Eisenbeis, C., A Strategy For Array Management in Local Memory, Inst. Nat. Recherche Inf. Autom., LeChesnay, France discusses a management strategy scheme which assists in determining when to load and unload portions of arrays and matrices into local memory and how to manage processor coherence.
See, also Aho, Sethi, Ullman, Compilers, Principles, Techniques, and Tools, Addison-Wesley Publishing Company (1985); and M. E. Wolf, Improving Locality and Parallelism in Nested Loops, Technical Report: CSL-TR-92-538, CSL, Dept. of EE and CS, Stanford University.
It would be desirable to achieve improved performance without compromising program correctness. It would especially helpful if a technique were available that operated on static information (during compile-time), and that provided a solution that addressed entire automatic variables independently of the programs source language.